#!/usr/bin/python
#-*- coding: utf-8 -*-
'''
Created on 2011-06-04

@author: adam
'''
import hashlib
import bisect
import threading


class ConsistentHashing(object):
    def __init__(self, nodes = [], D = 5):
        '''
        nodes - wezly do zhaszowania
        ring  - struktura reprezentujaca pierscien
        D     - liczba kopii danego wezla
        '''
        self.lock  = threading.Lock()
        self.nodes = nodes
        self.D     = D
        self._generate_circle()

    def reinit(self, nodes = [], D = 5):
        self.lock.acquire()
        self.nodes = nodes
        self.D     = D
        self._generate_circle()
        self.lock.release()

    def _generate_circle(self):
        tmp_list = []
        for node in self.nodes:
            for i in xrange(self.D):
                # #separator# + str(i) potrzebny jest, zeby jedna nazwe wezal rozhaszowac na D liczb
                h = self._hash_key(node + '#separator#' + str(i))
                tmp_list.append( (h,node) )
        tmp_list.sort()
        #posortowana wedlug haszy lista wezlow
        self.keys   = [i[1] for i in tmp_list]
        #posortowana lista haszy
        self.hashes = [i[0] for i in tmp_list]

    def _hash_key(self, key):
        #zwraca wartosc z przedzialu [0,1)
##        return (int(hashlib.md5(key).hexdigest(),16) % (2**31-1))/(2**31-1.)
        ascii_key = key.encode('ascii', 'ignore')
        return (int(hashlib.md5(ascii_key).hexdigest(),16) % (2**31-1))/(2**31-1.)

    def get_node(self, key):
        #dla danego zadania (key) zwraca wezel, ktory powinien go obsluzyc
        self.lock.acquire()
        h   = self._hash_key(key)
        #print h
        pos = bisect.bisect_left(self.hashes, h)
        if pos == len(self.hashes):
            pos = 0
        self.lock.release()
        return self.keys[pos]

    def add_node(self, node):
        self.lock.acquire()
        self.nodes.append(node)
        tmp_list = []
        for i in xrange(self.D):
            # #separator# + str(i) potrzebny jest, zeby jedna nazwe wezal rozhaszowac na D liczb
            h   = self._hash_key(node + '#separator#' + str(i))
            pos = bisect.bisect_left(self.hashes, h)
            self.hashes.insert(pos, h)
            self.keys.insert(pos, node)
        self.lock.release()

    def remove_node(self, node):
        self.lock.acquire()
        self.nodes.remove(node)
        tmp_list = [(h,n) for h,n in zip(self.hashes, self.keys) if n != node ]
        self.keys   = [i[1] for i in tmp_list]
        self.hashes = [i[0] for i in tmp_list]
        self.lock.release()






if __name__ == '__main__':
    consthash = ConsistentHashing(["a", "b", "c"])
    print consthash.keys
    print consthash.hashes
    print consthash.get_node("http://www.python.com/a")
    consthash.add_node("e")
    print consthash.keys
    print consthash.hashes
    print consthash.get_node("http://www.python.com/a")
    consthash.remove_node("e")
    print consthash.keys
    print consthash.hashes
    print consthash.get_node("http://www.python.com/a")
